package com.lzq.leetcode.hoot100;

import java.util.Arrays;
import java.util.List;

public class s139 {

    public boolean wordBreak(String s, List<String> wordDict) {

        int sLen = s.length();
        boolean[] dp = new boolean[sLen + 1];
        dp[0] = true;
        for (int i=0; i<sLen; i++) {
            if (!dp[i]) continue;

            for (String ds : wordDict) {

                if (i + ds.length() > sLen) continue;
                boolean flag = true;
                for (int k=0; k<ds.length(); k++) {

                    if (s.charAt(i + k) != ds.charAt(k)) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    dp[i + ds.length()] = true;
                    if (dp[sLen])   return true;
                }
            }
        }

        return false;
    }

    public static void main(String[] args) {
        s139 s139 = new s139();
        System.out.println(s139.wordBreak("leetcode", Arrays.asList(new String[]{"leet", "code"})));
    }
}
